#include <iostream>
#include <vector>

using namespace std;

#include "cgal_helper.h"
#include "Prim_MST.h"

Prim_MST::Prim_MST(vector<Point> p_list): p_list(p_list) {
}

int Prim_MST::longest_edge(int p_i, int p_idx[]) {
  int idx = 0;
  for (int i = 1; i < 3; i++) {
    if (Segment(p_list [p_i], p_list [p_idx [i]]).squared_length() > Segment(p_list [p_i], p_list [p_idx[idx]]).squared_length()) 
      idx = i;
  }
  return idx;
}

void Prim_MST::insert_non_duplicate_edges(pair<int,int> s , vector<pair<int,int> > &s_list) {
  bool found  = false;

  for (unsigned int i = 1; i < s_list.size(); i++) {
    if ((s_list [i].first == s.first && s_list [i].second == s.second)
      || (s_list [i].second == s.first && s_list [i].first == s.second)) {
      found = true;
      break;
    }
  }

  if (!found)
    s_list.push_back(s);
}

vector<pair<int,int> > Prim_MST::run() {
  vector<pair<int,int> > s_list;
  bool bitmap[p_list.size()];

  //Initialize Bitmap.
  for (unsigned int i = 0; i < p_list.size(); i++)
    bitmap [i]  = false;

  for (unsigned int i = 0; i < p_list.size(); i++) {
    int p_idx [3];

    p_idx [0] = (i+1)%p_list.size();
    p_idx [1] = (i+2)%p_list.size();
    p_idx [2] = (i+3)%p_list.size();

    if (bitmap [i] == true)
      continue;
    else
      bitmap [i]  = true;

    for (unsigned int j = i+4; j!=i; j=(j+1)%p_list.size()) {
      int idx = longest_edge(i, p_idx);
      
      if (Segment(p_list [i], p_list [j]).squared_length() < Segment(p_list [i], p_list [p_idx [idx]]).squared_length()) {
        p_idx [idx] = j;
      }
    }

    insert_non_duplicate_edges(make_pair(i, p_idx [0]), s_list);
    insert_non_duplicate_edges(make_pair(i, p_idx [1]), s_list);
    insert_non_duplicate_edges(make_pair(i, p_idx [2]), s_list);
  }
  return s_list;
}
